package com.yuqian.JavaSe.sort;

import java.util.Random;

/**
 * 快速排序
 * @author yy
 *
 */
public class FastSort {
	
	/**
	 *  返回数组划分的位置
	 * @param arr
	 * @param left
	 * @param right
	 * @return
	 */
	private static int fast(int[] arr,int left,int right) {
		int compare =arr[left];
		while(right>left) {
			//先从右侧开始找到比compare小的值 交换
			while(right>left&&compare<=arr[right]) {
				right--;
			}
			arr[left]=arr[right];
			//从左侧开始找到比compare大的值与 right交换
			while(right>left&&compare>=arr[left]) {
				left++;
			}
			arr[right] =  arr[left];
		}
		//将compare放到数组划分位置
		arr[right] =compare;
		return right;
	}
	
	
	public static void fastSort(int[] arr,int left,int right) {
		if(right<=left) {
			return;
		}
		int mid = fast(arr,left,right);
		//对左边排序
		fastSort(arr,left,mid-1);
		//对右边排序
		fastSort(arr,mid+1,right);
	}
	
	
	public static void fastSort(int[] arr) {
		fastSort(arr,0,arr.length);
	}
	private static void printArrays(int[] arr) {
		for(int k:arr) {
			System.out.print(k+" ,");
		}
		System.out.println();
	}
	


	
	public static void main(String[] args) {
		int length = 1000000;
		int[] arr =new int[length];
		Random r =new Random();
		for(int i=0;i<length;i++) {
			arr[i] = r.nextInt(100);
		}
		int[] kk=arr;
		long start1 = System.currentTimeMillis();
		fastSort(arr);
		printArrays(arr);
		System.out.println("fast time:  "+(System.currentTimeMillis()-start1));
		
		long start2 = System.currentTimeMillis();
		BubblingSort.bubbling(kk);
		printArrays(kk);
		System.out.println("bubbling time:  "+(System.currentTimeMillis()-start2));
		
	}
}
